2  Permutations

You will recall that we studied permutations in Abstract Algebra. A permutation is a bijective mapping from a set to itself. Since permutations are important in the study of finite groups we will start our investigation of group classification by expanding on what we learned about permutations in the Abstract Algebra module. Remember that we were able to represent permutations first as disjoint cycles and then as products of transpositions. The number of transpositions in a product determines whether the permutation is even or odd (it cannot be both). We used cycle (orbit) lengths to calculate the order (period) of a permutation in its group.

Example 2.1 Consider the permutation \[f = \begin{pmatrix} 1&2&3&4&5&6&7&8&9&10\\ 6&10&8&1&5&9&3&7&4&2 \end{pmatrix} \in S_{10}\]

We can express \(f\) as a product of disjoint cycle (recalling that we ignore singletons) \[\begin{align*} f&= (1 \; 6 \; 9 \; 4)(2 \; 10) (3 \; 8 \; 7)(5) \\ &= (1 \; 6 \; 9 \; 4)(2 \; 10) (3 \; 8 \; 7). \end{align*}\] We can express \(f\) as a product of transpositions as: \[\begin{align*} f&= (1 \; 4)(1 \; 9)(1\; 6) (2 \; 10) (3 \; 7)(3 \; 8) \end{align*}\] Thus \(f\) is an even as it can be written as a product of an even (6 in this case) number of transpositions.

2.1 Cayley’s Theorem

Cayley’s Theorem tells us that every finite group is isomorphic to some group of permutations. One way of seeing this is to simply read off the rows of the Cayley table for a group as permutations of the elements themselves.

Example 2.2 Consider the group given by the Cayley table below. \[ \begin{array}{c|cccccc} &0&1&2&3&4&5\\ \hline 0&0&1&2&3&4&5\\ 1&1&2&0&5&3&4\\ 2&2&0&1&4&5&3\\ 3&3&4&5&0&1&2\\ 4&4&5&3&2&0&1\\ 5&5&3&4&1&2&0 \end{array} \]

\[0\mapsto \begin{pmatrix} 0&1&2&3&4&5\\ 0&1&2&3&4&5 \end{pmatrix} \quad 1\mapsto \begin{pmatrix} 0&1&2&3&4&5\\ 1&2&0&5&3&4 \end{pmatrix} \quad 2\mapsto \begin{pmatrix} 0&1&2&3&4&5\\ 2&0&1&4&5&3 \end{pmatrix} \] \[3\mapsto \begin{pmatrix} 0&1&2&3&4&5\\ 3&4&5&0&1&2 \end{pmatrix} \quad 4\mapsto \begin{pmatrix} 0&1&2&3&4&5\\ 4&5&3&2&0&1 \end{pmatrix} \quad 5\mapsto \begin{pmatrix} 0&1&2&3&4&5\\ 5&3&4&1&2&0 \end{pmatrix} \]

We say that we have represented the group as a group of permutations. Notice that we can represent each of the group elements by the permutation of the column border defined by its row. Consider the group element 2 above. If we pre-multiply by 2 each of the elements of the group in their column border order, then we get the elements re-ordered as in row 2. That is, \[\begin{equation*} 2 \mapsto \begin{pmatrix} 0&1&2&3&4&5\\ 2&0&1&5&3&4 \end{pmatrix} \end{equation*}\]

Of course, the elements of the group do not have to be numbers.

Example 2.3 Consider the group of symmetries of a rectangle: \[ \begin{array}{c|cccc} \circ&e&r_{\pi}&s_1&s_2\\ \hline e&e&r_{\pi}&s_1&s_2\\ r_{\pi}&r_{\pi}&e&s_2&s_1\\ s_1&s_1&s_2&e&r_{\pi}\\ s_2&s_2&s_1&r_{\pi}&e \end{array} \] In the same way as in Example 2.2, we can express \(r_{\pi}\), for example, as a permutation: \[ r_{\pi} \mapsto \begin{pmatrix} e & r_{\pi} & s_1 & s_2 \\ r_{\pi}&e&s_2&s_1&\ \end{pmatrix}. \]

In both of the above examples, and in general, we replace \(g \in G = \{g_1, g_2, \ldots, g_n\}\) by the permutation \[\begin{pmatrix} g_1&g_2&\ldots&g_n\\ gg_1&gg_2&\ldots&gg_n \end{pmatrix}\] This is called the left regular representation of \(g\) and is denoted \(\lambda_g\). So, we have that \(\lambda_g(x) = gx, \; \forall x \in G\). It is important to note, at this point, that when we say that every finite group is isomorphic to a group of permutations we do not necessarily mean the full symmetry group itself; it is more likely to be a subgroup of the full symmetry group (for example, \(D_4\) has order 8 but there is no \(S_n\) with order 8 for any \(n\) and so \(D_4\) will be isomorphic to some subgroup of \(S_4\) of order 8).

Theorem 2.1 (Cayley’s Theorem) Every finite group is isomorphic to a group of permutations.

Proof.

For each \(a \in G\) define \(\lambda_{a}: G \to G\) by \(x \mapsto ax\). Notice that \(\lambda_{a}\) is a permutation of \(G\) since it has an inverse \(\lambda_{a^{-1}}\).

Set \(G' = \{\lambda_{a} \mid a \in G\}\). Then \(G'\) is a subgroup of the group of permutations of \(G\). This follows as for \(a,b \in G\): \[\begin{align*} \lambda_{a}\circ\lambda(b)(x) &= \lambda_a(bx) \\ &= abx \\ &= \lambda_{ab}(x) \end{align*}\] for all \(x \in G\). Therefore \(\lambda_a \circ \lambda_{b} = \lambda_{ab} \in G\). Further observe that \(|G'| = |G|\). This is because for \(a,b \in G\) with \(a \ne b\), \(\lambda_{a} \ne \lambda_{b}\). For instance \(\lambda_{a}(e) = a \ne b = \lambda_{b}(e)\).

Let \(\theta: G \to G'\) be the map defined by \(\theta(a) = \lambda_a\) for all \(a \in G\). Then \(\theta\) is a bijection. Thus, to see that \(\theta\) is an isomorphism, we only need show that it is a homomorphism. Let \(a, b \in G\), \[\theta(ab) = \lambda_{ab} = \lambda_{a}\circ \lambda_{b} = \theta(a) \circ \theta_{b}.\] Therefore \(\theta\) is a homomorphism and so an isomorphism.

Lastly observe that the group of permutations of \(G\) is isomorphic to \(S_{|G|}\). We conclude that \(G\) is therefore isomorphic to a subgroup of \(S_{|G|}\).

Notice what we did in that proof. First, we demonstrated that for each \(a \in G\) then \(\lambda_a\) is indeed a permutation and we did that by showing that \(\lambda_a\) is a bijective function from \(G\) to itself (because the set is finite it is sufficient to show injectivity). Second, we took the set of all \(\lambda_a\), for a given \(a \in G\), and demonstrated that this set forms a subgroup of \(S_n\) (as the set is finite we need only show closure). Third, we defined a function, \(\theta\), mapping from our group \(G\) to the subgroup of \(S_n\) (which we denoted \(\gp\)), and proved that was an isomorphism in the usual way. A reasonable question to ask at this point is why study abstract groups at all? If every finite group is isomorphic to some group of permutations then why not just study permutation groups? Well, often we do study groups via permutations, but any given finite group can be represented by permutation groups in infinitely many different ways and it is not always obvious which way is the most convenient or appropriate. For example, notice that the group in Example 2.2 is, in fact, isomorphic to \(S_3\), the symmetric group of order 6, and yet the proof of Cayley’s Theorem represents the group as a subgroup of \(S_6\). Secondly there are lots of other ways of representing groups and some ways are better than others depending on what we are trying to do or find out. The permutations above have been written in two row notation. We will usually adopt cycle notation and because permutations are functions, and multiplication of permutations is function composition, we will compose (or multiply) permutations from right to left (as you did in the Abstract Algebra module).

Example 2.4  

Returning to Example 2.2 once more. We compute \(\lambda_2 \circ \lambda_3\): \[ \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 1 & 4 & 5 & 3 \end{pmatrix} \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 0 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 3 & 2 & 0 & 1 \end{pmatrix}. \]

Thus \(\lambda_2 \circ \lambda_3 = \lambda_4\).

We can express this in cycle notation.

\[ (0 \; 2 \; 1)(3 \; 4 \; 5)(0 \; 3)(1 \; 4) (2 \; 5) = (0 \; 4)(1 \; 5)(2 \; 3). \]

2.2 Cycle Structure

Recall that the symmetric group of degree \(n\) is the set of all permutations of \(n\) things (usually the numbers from 1 up to \(n\)). The group is denoted \(S_n\) and since there are \(n!\) ways to permute or order \(n\) objects, then we have that \(|S| = n!\). The cycle structure of a permutation is its structure as a collection of disjoint cycles which can be described by replacing each of the symbols with a \(*\). For example, the cycle structure of \((1 \; 2)(3 \; 4 \; 5)(6 \; 7)\) is \((* \; *)(* \; * \; *)(* \; *)\), which we can also write as \((* \;*)(* \; *)(* \; * \; *)\) or even \((* \; *)^2(* \; * \; *)\), remembering that disjoint cycles commute. Permutations with the same cycle structure have similar properties, for example they have the same order because the order of any permutation is the lowest common multiple of the lengths of its disjoint cycles.

Example 2.5  

The possible cycle structures in \(S_3\) are: \[I, (\ast \; \ast), (\ast \; \ast \; \ast).\]

For a \(2\)-cycle, there are \(3\) choices for the first element and then \(2\) for the second giving a total of six \(2\)-cycles:

\[ (1 \; 2), (1 \; 3), (2 \; 1), (2 \; 3), (3 \; 1) (3 \; 2). \]

However, a the cycles \((a \; b)\) is the same as the cycle \((b \; a)\). Therefore, we have a total of \(3\) distinct \(2\)-cycles: \[ (1 \; 2), (1 \; 3), (2 \; 3). \]

In a similar way there are \(3!/3 = 2\) distinct \(3\)-cycles. Since the total number of \(3\)-cycles is \(3!\), we divide by \(3\) to get the number of distinct cycles since we have the equalities \[(a \; b \; c) = (b \; c \; a) = (c \; a \; b)\] for a cycle \((a \; b \; c)\).

So \[S_3 = \{I, (1 \; 2), (1 \; 3), (2 \; 3), (1 \; 2 \; 3), (1\; 3 \; 2) \}.\]

Note that \(|S_3| = 3! = 6\).

For \(S_4\) we haven:

\[ \begin{array}{c|c} \text{Structure} & \text{number} \\ \hline I & 1 \\ (\ast \; \ast) & 6 = \frac{4\times 3}{2} \\ (\ast \; \ast \; \ast) & 8 = \frac{4 \times 3 \times 2}{3} \\ (\ast \; \ast \; \ast \; \ast) & 6 = \frac{4 \times 3 \times 2}{4} \\ (\ast \; \ast) (\ast \; \ast) & 3 = \frac{4 \times 3 \times 2}{2 \times 2 \times 2} \\ \end{array} \] Notice that \[|S_4| = 1 + 6 + 8 + 6 + 3 = 24 = 4!.\]

2.3 Conjugates

We begin with a definition.

Definition 2.1 (Conjugate) If \(a\) and \(b\) are permutations (defined on the same set) then the conjugate of \(a\) by \(b\) is the permutation \(bab^{-1}\).

Later we shall extend the definition of conjugacy, in the obvious way, to group elements in general but for now we concentrate on permutations and hopefully get some idea as to why conjugacy is such a useful concept.

Example 2.6  

Let \(a = (1 \; 2 \; 3)(4 \; 5), b = (1 \; 6 \; 2 \; 4 \; 3) \in S_6\). The the conjugate of \(a\) by \(b\) is: \[\begin{align} bab^{-1} &= (1 \; 6 \; 2 \; 4 \; 3) (1 \; 2 \; 3)(4 \; 5) (1 \; 3 \; 4 \; 2 \; 6) \\ &= (1 \; 6 \; 4)(3 \; 5) \end{align}\]

Note that \(a\) and \(bab^{-1}\) have the same cycle structure: \[(\ast \; \ast \; \ast)(\ast \; \ast).\]

Less obvious is the fact that \(bab^{-1}\) can be obtained from \(a\) by replacing each element in each cycle of the disjoint cycle of a by its image under \(b\). That is:

\[\begin{align} a & = (1 \; 2 \; 3)(4 \; 5) \\ bab^{-1} &= (b(1) \; b(2) \; b(3))(b(4) \; b(5)) \\ &= (6 \; 4 \; 1)(3 \; 5) \\ &= (1 \; 6 \; 4)(3 \; 5). \end{align}\]

The next theorem demonstrates that the above holds true in general.

Theorem 2.2 The conjugate of \(a = (x_1 \; x_2 \; \ldots \; x_r) (y_1 \; y_2 \; \ldots \; y_s) \ldots (z_1 \; z_2 \; \ldots \; z_t)\) by \(b\) is \[c = (b(x_1) \; b(x_2) \; \ldots \; b(x_r)) (b(y_1) \; b(y_2) \; \ldots \; b(y_s)) \ldots (b(z_1) \; b(z_2) \; \ldots \; b(z_t)),\] where \(a\) has been expressed as a product of disjoint cycles.

Proof.

It suffices to show that \(ba = cb\) since, post-multiplying by \(b\), this implies that \(bab^{-1} = c\).

Let \(x\) be an element not fixed by \(a\). Without loss of generality we may assume that \(x= x_1\). We then have: \[\begin{align*} ba(x_1) &= b(x_2)\\ cb(x_1) &= b(x_2) \end{align*}\]

If \(x\) is fixed by \(a\) then: \[\begin{align*} ba(x) &= b(x)\\ cb(x) &= b(x) \end{align*}\]

Hence, \(ba = cb\) as required.

Definition 2.2 (Conjugacy) Let \(a\), \(b\) and \(c\) be permutations (defined on the same set). Then \(a\) is conjugate to \(c\) means that there exists a permutation \(b\) such that \(c = bab^{-1}\).

If \(c\) is the conjugate of \(a\) by \(b\), then \(a\) is the conjugate of \(c\) by \(b^{-1}\). This can be seen as follows: \[\begin{align} c &= bab^{-1} \\ \iff b^{-1}c &= ab^{-1}\\ \iff b^{-1}cb &=a. \end{align}\]

This show that the relation \(R\) on a group \(G\) that relates two elements whenever they are conjugate to to one another is symmetric. One can show that this relation is reflexive and transitive and, consequently, is an equivalence relation.

Corollary 2.1 Two permutations are conjugate if and only if they have the same cycle structure.

Proof.

This follows from the proof of Theorem 2.2.

Example 2.7  

Let \(a = (1 \; 5 \; 2 \; 4 )(3 \; 7)\) and \(c= (1 \; 6)(2 \; 4 \; 3 \; 5)\) be elements of \(S_7\). Clearly \(a\) and \(c\) have the same cycle structure and so must be conjugate. We can find an element in \(S_{7}\) that conjugates \(a\) to \(c\) by finding an element \(b\) satisfying \[\begin{align} (b(1) \; b(5) \; b(2) \; b(4)) &= (2 \; 4 \; 3 \; 5)\\ (b(3) \; b(7)) &= (1 \; 6 ). \end{align}\]

For example \(b = (1 \; 2 \; 3) (4 \; 5)(6 \; 7)\) works.

2.4 The 15-Puzzle

The original 15-puzzle is a tray with 15 numbered tiles that are free to slide into a single blank space but may not be removed from the tray. \[ \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&11&12\\ \hline 13&14&15&\\ \hline \end{array} \] After jumbling the pieces thoroughly the object is to bring them back into the above solved state. This puzzle was marketed by the American puzzle maker Sam Loyd in the 1890s, the resulting craze was fuelled by Loyd’s offer of a $1,000 prize for anyone who could solve the puzzle starting from the state with 14 and 15 swapped. \[ \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&11&12\\ \hline 13&15&14&\\ \hline \end{array} \] One way to model this problem is to treat the blank space as tile number 16. The solution requires us to express the transposition \((14\ 15)\) as a product of transpositions each involving 16. Of course not all transpositions with 16 are allowed, for example our first move must be either \((12\ 16)\) or \((14\ 16)\) but each move results in tile 16 moving one space vertically or one space horizontally. Since tile 16 must end up in the same position it started we must have that the number of ‘’up’’ moves equals the number of ‘’down’’ moves and the number of ‘’left moves’’ equals the number of ‘’right moves’’. Hence the number of transpositions required for any solution is even but \((14\ 15)\) is clearly an odd permutation so no solution is possible (and Sam Loyd’s money was safe). The above analysis, although powerful and elegant, only tells us half the story. If we rearrange the tiles so that the empty space ends up where it started, then only even permutations of the remaining blocks are possible. A similar argument shows that if the empty space is allowed to end up somewhere else, then if the space is an even (odd) distance from its starting point then only even (odd) permutations are possible. But are all such permutations possible? The answer is yes and it follows from the following results about the Alternating Group.

Lemma 2.1 For \(n \geq 3\), \(A_n\) is generated by its 3-cycles.

Proof.

First observe that \(A_n\) contains all \(3\) cycles and so the group generated by all \(3\) cycles is a subgroup of \(A_{n}\).

Let \(g \in A_n\) then there are transpositions \(t_1, t_2, \ldots, t_{2_{k}}\) such that \(g = t_1 t_2 \ldots t_{2k}\). Write \(g = (t_1 t_2) (t_3 t_4) \ldots (t_{2k-1} t_{2k})\). For each odd \(i\) in the set \(\{1,\ldots, 2k\}\) there are three possibilities for \(t_{i}t_{i+1}\)

1. \(t_{i} = t_{i+1}\): in this case \(t_i t_{i+1} = I\).
2. \(t_i\) and \(t_{i+1}\) have a point in common.In this case there are \(a,b,c\) such that \(t_i = (a \; b)\) and \(t_{i+1} = (b \; c)\). Hence, \(t_{i}t_{i+1} = (a \; b \; c)\).
3. \(t_i\) and \(t_{i+1}\) have no point in common. In this case there are \(a,b,c,d\) such that \(t_i = (a \; b)\) and \(t_{i+1} = (c \; d)\). Observe that the equality \[t_i t_{i+1} = (a \; b) (c \; d) = (a \; c \; d)(a \; b \; d)\] holds in this case.

Therefore, whenever \(t_it_{i+1}\) is not trivial we may replace it with a 3-cycle or with a product of 3-cycles. We see that \(g\) can therefore be written as a product of 3-cycles. The result now follows.

Note the structure of that proof. We were required to show that \(A_n\) is generated by its 3-cycles. Let us assume that \(S\) is the set of all 3-cycles where, obviously, \(S\) will depend on \(n\). In the first part of the proof we demonstrated that \(S \subseteq A_n\) and in the second part that \(A_n \subseteq S\). Hence we showed that the sets are equal and so the result follows.

Theorem 2.3 For \(n \geq 3\), \(A_n\) is generated by its 3-cycles of the form \((1 \; 2 \; i)\).

Proof.

It suffices to show, by Lemma 2.1 that any 3-cycle can be written as a product of elements of the form \((1 \; 2 \; i)\) and their inverses.

Now \[\begin{align*} (1 \; a \; 2) (1 \; 2 \; c) (1 \; b \; 2)(1 \; 2 \; a) &= (1 \; 2 \; a)^{-1} (1 \; 2 \; c) (1 \; b \; 2)(1 \; 2 \; a) \\ &= (1 \; 2 \; a)^{-1} (1 \; b \; c) (1 \; 2 \; a) \\ &= (a \; b \; c). \end{align*}\] This concludes the proof.

Clearly the same result would hold if 1 and 2 were replaced by any other distinct symbols. We want to know which starting positions, with the empty space in the bottom right hand corner, can be rearranged back into the solved state: \[\begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&11&12\\ \hline 13&14&15&\\ \hline \end{array}\] Clearly these are precisely the states which can be reached by starting from the solved state. We know that these states (when expressed as permutations of the solved state) form a subgroup of \(A_{15}\), we want to show that it is all of \(A_{15}\) (or, equivalently, all the elements of \(A_{16}\) which fix 16). We will do this by showing that every 3-cycle of the form \((11\ 12\ i)\) is possible and, since these cycles generate \(A_{15}\), the result will follow. [The rest of this section is not examinable.]

We first construct the 3-cycle \((11\ 12\ 15)\) in a particular way. Start by moving the empty space away from the edge of the board by exchanging it with 12 and then 11: \[\begin{array}{ccc} \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&11&12\\ \hline 13&14&15&\\ \hline \end{array} & \leadsto & \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&&11\\ \hline 13&14&15&12\\ \hline \end{array} \end{array}\] Then rotate the tiles in the bottom right quadrant. \[\begin{array}{ccc} \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&&11\\ \hline 13&14&15&12\\ \hline \end{array} & \leadsto & \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&&15\\ \hline 13&14&12&11\\ \hline \end{array} \end{array}\] Finally, we undo the two moves we started with to get the space back in the corner. \[\begin{array}{ccc} \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&&15\\ \hline 13&14&12&11\\ \hline \end{array} & \leadsto & \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&15&11\\ \hline 13&14&12&\\ \hline \end{array} \end{array}\] Representing this state as a permutation of the solved state gives \((11\ 12\ 15)\) as desired. We can construct any 3-cycle of the form \((11\ 12\ i)\) for any piece \(i\not\in\{11,12,15\}\) by first moving the space away from the corner (as we did above), then applying some sequence of moves to place \(i\) into the place originally occupied by 15 without moving 11 or 12, and ending with the space in the same position as before. If we then rotate the bottom right corner pieces, as before, and reverse the previous moves we will obtain \((11\ 12\ i)\). For example, to obtain \((11\ 12\ 4)\): \[\begin{array}{ccc} \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&11&12\\ \hline 13&14&15&\\ \hline \end{array} & \leadsto & \begin{array}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 5&6&7&8\\ \hline 9&10&&11\\ \hline 13&14&15&12\\ \hline \end{array} \end{array}\]

Then identify a tour which passes through the space and 15 without hitting 11 or 12 (indicated in bold). Cycle this tour round to obtain place 4 in the position occupied by 15. \[\begin{array}{ccc} \begin{array}{|c|c|c|c|} \hline {\bf 1}&{\bf 2}&{\bf 3}&{\bf 4}\\ \hline {\bf 5}&6&{\bf 7}&{\bf 8}\\ \hline {\bf 9}&10&&11\\ \hline {\bf 13}&{\bf 14}&{\bf 15}&12\\ \hline \end{array} & \leadsto & \begin{array}{|c|c|c|c|} \hline {\bf 13}&{\bf 9}&{\bf 5}&{\bf 1}\\ \hline {\bf 14}&6&{\bf 3}&{\bf 2}\\ \hline {\bf 15}&10&&11\\ \hline {\bf 7}&{\bf 8}&{\bf 4}&12\\ \hline \end{array} \end{array}\]

Now cycle the bottom right quadrant so that the 4 moves to where the 11 is now: \[\begin{array}{ccc} \begin{array}{|c|c|c|c|} \hline { 13}&{ 9}&{5}&{ 1}\\ \hline { 14}&6&{ 3}&{ 2}\\ \hline { 15}&10&&11\\ \hline { 7}&{ 8}&{ 4}&12\\ \hline \end{array} & \leadsto & \begin{array}{|c|c|c|c|} \hline { 13}&{ 9}&{5}&{ 1}\\ \hline { 14}&6&{ 3}&{ 2}\\ \hline { 15}&10&&4\\ \hline { 7}&{ 8}&{ 12}&11\\ \hline \end{array} \end{array}\] Finally undo the bold cycle which carried 4 into the place occupied by 15 and then move the space back to the corner to obtain \((11\ 12\ 4)\). \[\begin{array}{ccccc} \begin{array}{|c|c|c|c|} \hline {\bf 13}&{\bf 9}&{\bf 5}&{\bf 1}\\ \hline {\bf 14}&6&{\bf 3}&{\bf 2}\\ \hline {\bf 15}&10&&4\\ \hline {\bf 7}&{\bf 8}&{\bf 12}&11\\ \hline \end{array} & \leadsto & \begin{array}{|c|c|c|c|} \hline {\bf 1}&{\bf 2}&{\bf 3}&{\bf 12}\\ \hline {\bf 5}&6&{\bf 7}&{\bf 8}\\ \hline {\bf 9}&10&&4\\ \hline {\bf 13}&{\bf 14}&{\bf 15}&11\\ \hline \end{array} & \leadsto & \begin{array}{|c|c|c|c|} \hline {1}&{2}&{3}&{12}\\ \hline {5}&6&{ 7}&{8}\\ \hline {9}&10&4&11\\ \hline { 13}&{ 14}&{15}&\\ \hline \end{array} \end{array}\] Because every 3-cycle \((11\ 12\ i)\) can be formed in this way and these 3-cycles generate \(A_{15}\) we can obtain every even permutation of the solved state. It follows that every even permutation of the solved state can be solved! There is a subtlety here though - we are permuting positions not tiles. For example, if we want to apply \((11\ 12\ 4)\) again so as to form the permutation \((11\ 12\ 4)^2=(11\ 4\ 12)\) then we need to repeat the actual moves we did before so that the tile in position 4 (which is now 12) moves into the space occupied by 15.

2.5 Problem Sheet 2

For Week 5; covers Chapter 2 material. At minimum you should attempt questions 2.2, 2.3, 2.9 and 2.10.

---

Question 2.1

Which of the following permutations is different from the other two: \[ (1\; 4\; 2\; 8)(3\; 7\; 5),\quad (1\; 8\; 2\; 4)(5\; 7\; 3),\quad (7\; 5\; 3)(2\; 8\; 1\; 4). \]

Solution 2.1

Note that disjoint cycles commute and cycles that have the same cyclic structure are the same as each other (e.g \((1\; 2\; 3\; 4) = (3\; 4\; 1\; 2)\)). Hence, using the above, we can see that \((1\; 4\; 2\; 8)(3\; 7\; 5) = (7\; 5\; 3)(2\; 8\; 1\; 4)\), but the middle one is different.

Question 2.2

Write down all of the permutations in \(S_5\) with each of the following cycle structures:

1. \((*\;*)\);
2. \((*\;*\;*\;*)\);
3. \((*\;*)(*\;*)\).

Solution 2.2

1. \[\begin{align*} &(1\; 2), \, (1\; 3), \, (1\; 4), \, (1\; 5), \, (2\; 3),\\ &(2\; 4), \, (2\; 5), \, (3\; 4), \, (3\; 5), \, (4\; 5). \end{align*}\]
2. \[\begin{align*} &(1\; 2\; 3\; 4), \; (1\; 2\; 3\; 5), \; (1\; 2\; 4\; 3), \; (1\; 2\; 4\; 5), \; (1\; 2\; 5\; 3), \; (1\; 2\; 5\; 4),\\ &(1\; 3\; 2\; 4), \; (1\; 3\; 2\; 5), \; (1\; 3\; 4\; 2), \; (1\; 3\; 4\; 5), \; (1\; 3\; 5\; 2), \; (1\; 3\; 5\; 4),\\ &(1\; 4\; 2\; 3), \; (1\; 4\; 2\; 5), \; (1\; 4\; 3\; 2), \; (1\; 4\; 3\; 5), \; (1\; 4\; 5\; 2), \; (1\; 4\; 5\; 3),\\ &(1\; 5\; 2\; 3), \; (1\; 5\; 2\; 4), \; (1\; 5\; 3\; 2), \; (1\; 5\; 3\; 4), \; (1\; 5\; 4\; 2), \; (1\; 5\; 4\; 3),\\ &(2\; 3\; 4\; 5), \; (2\; 3\; 5\; 4), \; (2\; 4\; 3\; 5), \; (2\; 4\; 5\; 3), \; (2\; 5\; 3\; 4), \; (2\; 5\; 4\; 3). \end{align*}\]
3. \[\begin{align*} &(1\; 2)(3\; 4), \; (1\; 2)(3\; 5), \; (1\; 2)(4\; 5), \; (1\; 3)(2\; 4), \; (1\; 3)(2\; 5), \; (1\; 3)(4\; 5),\\ &(1\; 4)(2\; 3), \; (1\; 4)(2\; 5), \; (1\; 4)(3\; 5), \; (1\; 5)(2\; 3), \; (1\; 5)(2\; 4), \; (1\; 5)(3\; 4), \\ &(2\; 3)(4\; 5), \; (2\; 4)(3\; 5), \; (2\; 5)(3\; 4) . \end{align*}\]

Question 2.3

Write down all of the cycle structures in \(S_6\) together with the number of each. [Do not attempt to list the permutations themselves!]

Solution 2.3

\[\begin{align*} & I \qquad 1 \\ & (*\; *) \qquad \frac{6 \times 5}{2} = 15 \\ & (*\; *\; *) \qquad \frac{6 \times 5 \times 4}{3} = 40 \\ & (*\; *\; *\; *) \qquad \frac{6 \times 5 \times 4 \times 3}{4} = 90 \\ & (*\; *\; *\; *\; *) \qquad \frac{6 \times 5 \times 4 \times 3 \times 2}{5} = 144 \\ & (*\; *\; *\; *\; *\; *) \qquad \frac{6!}{6} = 120 \\ & (*\; *)(*\; *) \qquad \left[\left(\frac{6 \times 5}{2}\right) \times \left(\frac{4 \times 3}{2}\right)\right] / 2 = \frac{15 \times 6}{2} = 45 \\ & (*\; *)(*\; *\; *) \qquad \left(\frac{6 \times 5}{2}\right) \times \left(\frac{4 \times 3 \times 2}{3}\right) = 120 \\ & (*\; *)(*\; *\; *\; *) \qquad \left(\frac{6 \times 5}{2}\right) \times \frac{4!}{4} = 90 \\ & (*\; *)(*\; *)(*\; *) \qquad \left[\left(\frac{6 \times 5}{2}\right) \times \left(\frac{4 \times 3}{2}\right) \times \left(\frac{2 \times 1}{2}\right)\right] / 3! = 15 \\ & (*\; *\; *)(*\; *\; *) \qquad \left[\left(\frac{6 \times 5 \times 4}{3}\right) \times \left(\frac{3!}{3}\right)\right] / 2 = 40 \end{align*}\]

Note that \(|S_6| = 720\) and the above numbers sum to \(720\). For \((*\; *\; *)(*\; *\; *)\) there are \(\frac{6 \times 5 \times 4}{3}\) choices for the first 3-cycle, which leaves \(\frac{3 \times 2 \times 1}{3} = 2\) choices for the second, so there are \(\frac{6 \times 5 \times 4}{3} \times \frac{3 \times 2 \times 1}{3}\) possible products. However, this counts each twice (for example, \((1\; 2\; 3)(4\; 5\; 6) = (4\; 5\; 6)(1\; 2\; 3))\). When counting \((*\; *)(*\; *\; *)\) there is no need for this final adjustment as there is no double counting!

Question 2.4

Write down the elements of \(A_4\).

Solution 2.4

\[\begin{align*} A_4 = \{&I,\, (1\; 2)(3\; 4),\, (1\; 3)(2\; 4),\, (1\; 4)(2\; 3),\, (1\; 2\; 3),\, (1\; 2\; 4),\, (1\; 3\; 2),\, (1\; 3\; 4),\, \\ &(1\; 4\; 2),\, (1\; 4\; 3),\, (2\; 3\; 4),\, (2\; 4\; 3)\}. \end{align*}\]

Question 2.5

Let \(a= (2\; 5\; 3)(4\; 6)\) and \(b= (1\; 2\; 6)\). Calculate:

1. \(ab\);
2. \(ba\);
3. \((ab)^{-1}\);
4. \(a^{-1}\);
5. \(b^{-1}\);
6. \(b^{-1}a^{-1}\).

Solution 2.5

We have:

1. \(ab= (2\; 5\; 3)(4\; 6)(1\; 2\; 6) = (1\; 5\; 3\; 2\; 4\; 6)\);
2. \(ba = (1\; 2\; 6)(2\; 5\; 3)(4\; 6) = (1\; 2\; 5\; 3\; 6\; 4)\);
3. \((ab)^{-1} = (1\; 5\; 3\; 2\; 4\; 6)^{-1} = (1\; 6\; 4\; 2\; 3\; 5)\);
4. \(a^{-1} = (4\; 6)(2\; 3\; 5)\)
5. \(b^{-1} = (1\; 6\; 2)\);
6. \(b^{-1}a^{-1} = (ab)^{-1} = (1\; 6\; 4\; 2\; 3\; 5)\).

Question 2.6

Write down the orders of the following permutations:

1. \((1\; 2\; 3\; 4\; 5)\);
2. \((1\; 2\; 3\; 4\; 5)(7\; 8)\);
3. \((1\; 2\; 3\; 4\; 5\; 6)(7\; 8)\);
4. \((1\; 2)( 3\; 4)( 5\; 6)(7\; 8)\);
5. \((1\; 5)(2\; 3\; 5\; 4)\).

Solution 2.6

We will denote by \(|g|\) the order of a group element \(g\). Recall that to find the order of a permutation we take the lowest common multiple of the lengths of the disjoint cycles.

1. \(|(1\; 2\; 3\; 4\; 5)| = 5\);
2. \(| (1\; 2\; 3\; 4\; 5)(7\; 8) | = 10\);
3. \(| (1\; 2\; 3\; 4\; 5\; 6)(7\; 8) | = 6\);
4. \(| (1\; 2)( 3\; 4)( 5\; 6)(7\; 8) | = 2\);
5. \(| (1\; 5)(2\; 3\; 5\; 4) | = | (1\; 5\; 4\; 2\; 3) | = 5\).

Question 2.7

In each of the following cases find the order of \(ab\):

1. \(a= (1\; 2)\) and \(b= (1\; 2\; 3)\);
2. \(a= (4\; 5)\) and \(b= (1\; 2\; 3)\);
3. \(a=(1\; 4)\) and \(b= (1\; 2\; 3)\);
4. \(a= (1\; 2)(3\; 4)\) and \(b= (1\; 2\; 3)\);
5. \(a= (3\; 4)(5\; 6)\) and \(b= (1\; 2\; 3)(4\; 5\; 6)\);
6. \(a= (3\; 4)(6\; 7)\) and \(b= (1\; 2\; 3)(4\; 5\; 6)(7\; 8\; 9)\).

Solution 2.7

1. \(ab = (1\; 2)(1\; 2\; 3) = (1)(2\; 3)\). So, \(|ab| = 2\).
2. \(ab = (4\; 5)(1\; 2\; 3)\). So, \(|ab| = 6\).
3. \(ab = (1\; 4)(1\; 2\; 3) = (1\; 2\; 3\; 4)\). So, \(|ab| = 4\).
4. \(ab = (1\; 2)(3\; 4)(1\; 2\; 3) = (1)(2\; 4\; 3)\). So, \(|ab| = 3\).
5. \(ab = (3\; 4)(5\; 6)(1\; 2\; 3)(4\; 5\; 6) = (1\; 2\; 4\; 6\; 3)\). So, \(|ab| = 5\).
6. \(ab = (3\; 4)(6\; 7)(1\; 2\; 3)(4\; 5\; 6)(7\; 8\; 9) = (1\; 2\; 4\; 5\; 7\; 8\; 9\; 6\; 3)\). So, \(|ab| = 9\).

Question 2.8

Given \(N \in \N\), show that there is a number \(n \in \N\) and elements \(a, b \in S_n\) such that

• \(a^2 = I\),
• \(b^3 = I\), and,
• the order of \(ab\) is greater than \(N\).

Solution 2.8

We just need to generalise part vi. of Question 2.7 above. Let \(a = (3\; 4)(6\; 7)\ldots(3n\; 3n+1)\) and \(b =(1\; 2\; 3)(4\; 5\; 6)(7\; 8\; 9)\ldots(3n+1\; 3n+2\; 3n+3)\) be elements of \(S_n\). Then \(|a| = 2\), \(|b| = 3\) and \(|ab| = 3n+3\) for any \(n \in \N\).

Question 2.9

Find the largest order for an element of \(S_{10}\).

Solution 2.9

For \(f \in S_{10}\), \(|f|\) is the lowest common multiple of the lengths of the disjoint cycles. (i.e. the lcm of the sizes of the orbits of \(f\)). By considering likely candidates, a 10-cycle has order 10, a 9-cycle and a 1-cycle has order 9, an 8-cycle and a 2-cycle has order 8, but a 3-cycle and a 7-cycle has order 21. This looks best possible until we consider a 2-cycle, 3-cycle and 5-cycle which has order 30. (How could this have been deduced without trial and error?)

Question 2.10

In each of the following cases find the conjugate of \(a\) with \(b\), i.e. compute \(bab^{-1}\):

1. \(a= (1\; 2)\) and \(b= (2\; 3\; 4\; 5)\);
2. \(a= (1\; 3)(2\; 5\; 6)\) and \(b= (2\; 3)(4\; 5)\);
3. \(a= (1\; 4)(2\; 5)\) and \(b= (1\; 3\; 2\; 5)\);
4. \(a= (1\; 2)(3\; 4)\) and \(b= (1\; 2\; 3)\);
5. \(a= (1\; 3\; 2\; 5)\) and \(b= (1\; 4)(2\; 5)\);
6. \(a= (1\; 5\; 6)\) and \(b= (1\; 5\; 6)\).

Solution 2.10

1. \(bab^{-1} = (1\; 3)\);
2. \(bab^{-1} = (1\; 2)(3\; 4\; 6)\);
3. \(bab^{-1} = (3\; 4)(5\; 1)\);
4. \(bab^{-1} = (2\; 3)(1\; 4)\);
5. \(bab^{-1} = (4\; 3\; 5\; 2)\);
6. \(bab^{-1} = (5\; 6\; 1) = a\), as expected.

Question 2.11

In each of the following cases find, where possible, permutations \(b\in S_6\) and \(d \in A_{6}\) such that \(bab^{-1}=c = dad^{-1}\):

1. \(a= (1\; 3\; 2)(4\; 5)\), and \(c= (1\; 5)(2\; 3\; 4)\);
2. \(a= (1\; 4)(2\; 3)\), and \(c= (1\; 6)(2\; 4)(3\; 5)\);
3. \(a= (1\; 2)(3\; 4)\), and \(c= (1\; 3)( 2\; 4)\);
4. \(a= (1\; 4)\), and \(c= I\);
5. \(a= (1\; 3)\), and \(c= (1\; 3)\).

Solution 2.11

1. For \(a= (1\; 3\; 2)(4\; 5)\), and \(c= (1\; 5)(2\; 3\; 4)\), we can take \[b = (1\; 2\; 4).\]
2. For \(a= (1\; 4)(2\; 3)\), and \(c= (1\; 6)(2\; 4)(3\; 5)\), there is no such \(b\) as \(a\) and \(c\) have different cycle structures.
3. For \(a= (1\; 2)(3\; 4)\), and \(c= (1\; 3)( 2\; 4)\) we can take \[b = (2\; 3).\]
4. For \(a= (1\; 4)\), and \(c= I\), there is no such \(b\).
5. For \(a= (1\; 3)\), and \(c= (1\; 3)\) we can take \[b=I.\]

Question 2.12

Let \(n \ge 5\). Let \(a, c \in A_{n}\) be 3-cycles. Show that there is an element \(b \in A_n\) such that \(bab^{-1} = c\).

Does the statement above hold when \(n \in \{3,4\}\)?

[Hint: For the first part of the question, find a conjugate in \(S_n\); if it is not an element of \(A_n\) how can you make it into an elmement of \(A_n\) using the fact that disjoint cycles commute?]

Solution 2.12

Clearly there is an element \(b \in S_n\) such that \(bab^{-1} = c\). If \(b\) is an element of \(A_n\) we are done. Therefore, suppose \(b\) is not an element of \(A_n\). Let \(i,j \in \{1,2,\ldots, n\}\) be such that \(a(i)=i\) and \(a(j) = j\). Notice that \(i\) and \(j\) exists since \(a\) is a three-cycle and \(n \ge 5\). Thus the element \(b (i \ j)\) is an element of \(A_n\). Moreover, as \((i \ j)\) is disjoing from \(a\), we have \[b(i \ j) a (i \ j) b^{-1} =ba(i \ j)(i \ j)b^{-1} = bab^{-1} = c\] as required.

Notice that \(A_3 = \{(1 \ 2 \ 3), (1 \ 3 \ 2), ()\}\cong \Z_{3}\) is abelian and so its two three cycles cannot be conjugate to one another.

Now consider the elements \((1 \ 2 \ 3)\) and \((1 \ 3 \ 2)\) in \(A_{4}\). Suppose \(b \in A_4\) is such that \(b(1 \ 2 \ 3)b^{-1} = (1 \ 3 \ 2)\). Notice that it must be the case that \(\{b(1), b(2), b(3)\} = \{1, 2, 3\}\). Thus there is an element \(b' \in S_{3}\) such that \(b'(1 \ 2 \ 3)(b')^{-1} = (1 \ 3 \ 2)\). However, we have already seen that no such element exists.